#define _CRT_SECURE_NO_WARNINGS

int Part1Sort(int* arr, int left, int right)
{
	int keyi = left;
	while (left < right)
	{
		while (left<right&&arr[right] >= arr[keyi])
			right--;
		while (left < right && arr[left] <= arr[keyi])
			left++;
		Swap(&arr[left], &arr[right]);
	}
	Swap(&arr[keyi], &arr[left]);
	return left;

}
int Part2Sort(int* arr, int left, int right)
{
	int hole = left;
	int key = arr[left];
	while (left < right)
	{
		while (left<right&&arr[right] >= key)
			right--;
		arr[hole] = arr[right];
		hole = right;

		while (left < right && arr[left] <= key)
			left++;
		arr[hole] = arr[left];
		hole = left;
	}
	arr[hole] = key;
	return hole;

}

int Part3Sort(int* arr, int left, int right)
{
	int keyi = left;
	int pre = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (arr[cur] < arr[keyi]&&++pre!=cur)
		{
			Swap(&arr[cur], &arr[pre]);
		}
		cur++;
	}
	Swap(&arr[keyi], &arr[pre]);
	return pre;

}

